package com.wc.data_structures.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author congge
 * @Date 2023/4/25 0:07
 * @description
 */
public class ThreadedBinaryTree<T> {

    public ThreadedBinaryTreeNode<T> pre = null;

    public ThreadedBinaryTreeNode<T> root;

    public ThreadedBinaryTree() {

    }

    public ThreadedBinaryTree(ThreadedBinaryTreeNode<T> root) {
        this.root = root;
    }

    public void inOrderThreaded() {
        inOrderThreaded(root);
    }

    /**
     * 中序线索化二叉树
     *
     * @param root 根
     */
    public void inOrderThreaded(ThreadedBinaryTreeNode<T> root) {
        if (root == null) {
            return;
        }
        // 左递归
        inOrderThreaded(root.left);

        // 处理前驱和后继
        if (root.left == null) {
            root.left = pre;
            root.leftType = 1;
        }
        if (pre != null && pre.right == null) {
            pre.right = root;
            pre.rightType = 1;
        }

        pre = root;
        // 右递归
        inOrderThreaded(root.right);
    }

    /**
     * 线性遍历线索二叉树
     */
    public List<T> threadedList() {
        ThreadedBinaryTreeNode<T> node = this.root;
        List<T> orderList = new ArrayList<>();


        while (node != null) {
            // 找到第一个leftType = 1
            while (node.leftType == 0) {
                node = node.left;
            }

            orderList.add(node.value);
            while (node.rightType == 1) {
                node = node.right;
                orderList.add(node.value);
            }

            node = node.right;
        }

        return orderList;
    }

    /**
     * 中序线索化（自己编写的）
     * 中序遍历一定有两个空指针
     */
    public void threaderNode(ThreadedBinaryTreeNode<T> root) {
        List<ThreadedBinaryTreeNode<T>> inOrderList = inOrder(root);
//        for (ThreadedBinaryTreeNode<T> tThreadedBinaryTreeNode : inOrderList) {
//            System.out.print(tThreadedBinaryTreeNode.value.toString() + " ");
//        }
        System.out.println();
        int size = inOrderList.size();
        if (size <= 2) {
            return;
        }
        inOrderList.get(0).leftType = 1;
        // 右滑
        for (int i = 0; i < size - 1; i++) {
            ThreadedBinaryTreeNode<T> preNode = inOrderList.get(i);
            ThreadedBinaryTreeNode<T> postNode = inOrderList.get(i + 1);
            if (preNode.right == null) {
                preNode.right = postNode;
                preNode.rightType = 1;
            }
        }
        // 左滑
        for (int i = size - 1; i > 0; i--) {
            ThreadedBinaryTreeNode<T> preNode = inOrderList.get(i - 1);
            ThreadedBinaryTreeNode<T> postNode = inOrderList.get(i);
            if (postNode.left == null) {
                postNode.left = preNode;
                postNode.leftType = 1;
            }
        }
        inOrderList.get(size - 1).rightType = 1;
    }


    private List<ThreadedBinaryTreeNode<T>> inOrder(ThreadedBinaryTreeNode<T> root) {
        List<ThreadedBinaryTreeNode<T>> inOrderList = new ArrayList<>();
        inOrder(root, inOrderList);
        return inOrderList;
    }

    private void inOrder(ThreadedBinaryTreeNode<T> root, List<ThreadedBinaryTreeNode<T>> inOrderList) {
        if (root == null) {
            return;
        }
        inOrder(root.left, inOrderList);
        inOrderList.add(root);
        inOrder(root.right, inOrderList);
    }
}
